package william.recursive;

import william.utils.ArrayUtils;

import java.util.Arrays;

/**
 * @author ZhangShenao
 * @date 2024/1/23
 * @description
 */
public class 找到数组中的最大值 {
    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArray(10, -100, 100);
        System.out.println("原始数组为: ");
        System.out.println(Arrays.toString(arr));
        int max = max(arr);
        System.out.println("最大值为: " + max);
    }

    /**
     * 返回数组arr中的最大值
     */
    public static int max(int[] arr) {
        //边界条件校验
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("array is empty!!");
        }

        //递归调用
        return maxRecursive(arr, 0, arr.length - 1);
    }

    /**
     * 递归调用:返回数组arr[L,R]范围内的最大值
     */
    private static int maxRecursive(int[] arr, int L, int R) {
        //递归终止条件
        if (L == R) {
            return arr[L];
        }

        //依次计算数组左、右两部分的最大值
        int mid = L + ((R - L) >> 1);

        int leftMax = maxRecursive(arr, L, mid);
        int rightMax = maxRecursive(arr, mid + 1, R);

        //最后返回两个最大值中的最大值
        return Math.max(leftMax, rightMax);
    }
}
